/*
 * Copyright (C) 2010 M. Hautle.
 * 
 * This file is part of SimpleEL.
 * 
 * SimpleEL is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or (at your option) any later version.
 * 
 * SimpleEL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License along with SimpleEL. If not, see <http://www.gnu.org/licenses/>.
 */
package ch.msoftch.internal;

import java.lang.ref.*;
import java.util.*;
import java.util.concurrent.locks.*;
import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock;
import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock;

/**
 * Cache using {@link Reference}s for keys and values and a {@link ReadWriteLock} for internal synchronization.<br>
 * 
 * @param <K> The key type
 * @param <V> The value type
 * @author M. Hautle
 */
public class LockedCache<K, V> implements ICache<K, V> {
    /** The default initial capacity -- MUST be a power of two. */
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    /** The maximum capacity, used if a higher value is implicitly specified by either of the constructors with arguments. MUST be a power of two <= 1<<30. */
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /** The load fast used when none specified in constructor. */
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /** The lock. */
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

    /** The read lock. */
    private final ReadLock read = lock.readLock();

    /** The write lock. */
    private final WriteLock write = lock.writeLock();

    /** Reference queue for the cleared keys. */
    private final ReferenceQueue<K> queue = new ReferenceQueue<K>();

    /** The table, resized as necessary. Length MUST Always be a power of two. */
    private Entry[] table;

    /** The number of key-value mappings. */
    private int size;

    /** The next size value at which to resize (capacity * load factor). */
    private int threshold;

    /** The load factor for the hash table. */
    private final float loadFactor;

    /**
     * Default constructor.
     */
    public LockedCache() {
        loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (DEFAULT_INITIAL_CAPACITY);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
    }

    /**
     * {@inheritDoc}
     */
    @SuppressWarnings("unchecked")
    public V get(K key) {
        expungeStaleEntries();
        final int h = hash(key.hashCode());
        read.lock();
        try {
            for (Entry<K, V> e = table[indexFor(h, table.length)]; e != null; e = e.next) {
                if (e.hash == h && eq(key, e.get()))
                    return e.getValue();
            }
            return null;
        } finally {
            read.unlock();
        }
    }

    /**
     * {@inheritDoc}
     */
    @SuppressWarnings("unchecked")
    public V put(K key, V value) {
        final int h = hash(key.hashCode());
        expungeStaleEntries();
        write.lock();
        try {
            final int i = indexFor(h, table.length);
            // exists already a entry with such a key?
            for (Entry<K, V> e = table[i]; e != null; e = e.next) {
                if (h == e.hash && eq(key, e.get()))
                    return e.setValue(value);
            }
            // create a new entry
            table[i] = new Entry<K, V>(key, value, queue, h, table[i]);
            if (++size >= threshold)
                resize(table.length * 2);
            return null;
        } finally {
            write.unlock();
        }
    }

    /**
     * Rehashes the contents of this map into a new array with a larger capacity. This method is called automatically when the number of keys in this map
     * reaches its threshold.
     * 
     * If current capacity is MAXIMUM_CAPACITY, this method does not resize the map, but sets threshold to Integer.MAX_VALUE. This has the effect of preventing
     * future calls.
     * 
     * @param newCapacity the new capacity, MUST be a power of two; must be greater than current capacity unless current capacity is MAXIMUM_CAPACITY (in which
     *            case value is irrelevant).
     */
    private void resize(int newCapacity) {
        final Entry[] oldTable = table;
        if (oldTable.length == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        final Entry[] newTable = new Entry[newCapacity];
        transfer(oldTable, newTable);
        table = newTable;

        /*
         * If ignoring null elements and processing ref queue caused massive
         * shrinkage, then restore old table.  This should be rare, but avoids
         * unbounded expansion of garbage-filled tables.
         */
        if (size >= threshold / 2) {
            threshold = (int) (newCapacity * loadFactor);
        } else {
            expungeStaleEntries();
            transfer(newTable, oldTable);
            table = oldTable;
        }
    }

    /**
     * Transfers all entries from src to dest table.
     * 
     * @param src The source table
     * @param dest The destination table
     */
    @SuppressWarnings("unchecked")
    private void transfer(Entry[] src, Entry[] dest) {
        for (int j = 0; j < src.length; ++j) {
            for (Entry<K, V> e = src[j]; e != null;) {
                final Entry<K, V> next = e.next;
                // key already GCed?
                if (e.get() == null) {
                    e.cleanUp();
                    size--;
                } else {
                    final int i = indexFor(e.hash, dest.length);
                    e.next = dest[i];
                    dest[i] = e;
                }
                e = next;
            }
            src[j] = null;
        }
    }

    /**
     * Expunges stale entries from the table.
     */
    @SuppressWarnings("unchecked")
    private void expungeStaleEntries() {
        // check for a stale entry before acquiring the lock!
        Entry<K, V> e = (Entry<K, V>) queue.poll();
        if (e == null)
            return;
        write.lock();
        try {
            for (; e != null; e = (Entry<K, V>) queue.poll()) {
                final int i = indexFor(e.hash, table.length);
                Entry<K, V> prev = table[i];
                Entry<K, V> p = prev;
                while (p != null) {
                    final Entry<K, V> next = p.next;
                    if (p == e) {
                        if (prev == e)
                            table[i] = next;
                        else
                            prev.next = next;
                        e.cleanUp();
                        size--;
                        break;
                    }
                    prev = p;
                    p = next;
                }
            }
            // TODO shrink map?
        } finally {
            write.unlock();
        }
    }

    /**
     * {@inheritDoc}
     */
    public void clear() {
        write.lock();
        try {
            clearQueue();
            Arrays.fill(table, null);
            size = 0;
            clearQueue();
        } finally {
            write.unlock();
        }
    }

    /**
     * Clears the {@link #queue} by polling it.
     */
    private void clearQueue() {
        write.lock();
        try {
            while (queue.poll() != null)
                ;
        } finally {
            write.unlock();
        }
    }

    /**
     * Improves the given hash value.<br>
     * Same implementation as HashMap.hash().
     * 
     * @param h The original hash
     * @return An improved hash
     */
    private static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /**
     * Checks tow elements on equality.
     * 
     * @param o1 The first value
     * @param o2 The second value or null
     * @return True if they are equals
     */
    private static boolean eq(Object o1, Object o2) {
        return o1 == o2 || o1.equals(o2);
    }

    /**
     * Returns the index for the given hash.
     * 
     * @param h The hash
     * @param length The table length
     * @return The index
     */
    private static int indexFor(int h, int length) {
        return h & (length - 1);
    }

    /**
     * {@link Reference} holding the key.
     * 
     * @param <K> The key type
     * @param <V> The value type
     * @author M. Hautle
     */
    private static class Entry<K, V> extends SoftReference<K> {
        /** The hash of the key. */
        final int hash;

        /** The entry value hold in a {@link Reference}. */
        private Reference<V> value;

        /** The next entry. */
        Entry<K, V> next;

        /**
         * Default constructor.
         * 
         * @param key The key
         * @param value The value
         * @param queue The reference queue for the key
         * @param hash The keys hash value
         * @param next The next entry
         */
        Entry(K key, V value, ReferenceQueue<K> queue, int hash, Entry<K, V> next) {
            super(key, queue);
            this.value = new SoftReference<V>(value);
            this.hash = hash;
            this.next = next;
        }

        /**
         * Returns the value or null if it was already cleared.
         * 
         * @return The value or null
         */
        public V getValue() {
            return value.get();
        }

        /**
         * Sets the given value as new value.
         * 
         * @param newValue The new value
         * @return The old value or null
         */
        public V setValue(V newValue) {
            V oldValue = getValue();
            value = new SoftReference<V>(newValue);
            return oldValue;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Entry))
                return false;
            final Entry e = (Entry) o;
            final Object k1 = get();
            final Object k2 = e.get();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                final Object v1 = getValue();
                final Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public int hashCode() {
            return hash;
        }

        /**
         * Cleans up the content of this entry. Thus to help GC.
         */
        public void cleanUp() {
            value = null;
            next = null;
        }
    }
}
